﻿//为高尔夫比赛砍树(hard):https://leetcode.cn/problems/cut-off-trees-for-golf-event/
class Solution
{
	int m, n;
public:
	int cutOffTree(vector<vector<int>>& f)
	{
		m = f.size(), n = f[0].size();
		// 1. 准备⼯作：找出砍树的顺序
		vector<pair<int, int>> trees;
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (f[i][j] > 1) trees.push_back({ i, j });

		sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const
			pair<int, int>& p2)
			{
				return f[p1.first][p1.second] < f[p2.first][p2.second];
			});
		// 2. 按照顺序砍树
		int bx = 0, by = 0;
		int ret = 0;
		for (auto& [a, b] : trees)
		{
			int step = bfs(f, bx, by, a, b);
			if (step == -1) return -1;
			ret += step;
			bx = a, by = b;
		}
		return ret;
	}
	bool vis[51][51];
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey)
	{
		if (bx == ex && by == ey) return 0;
		queue<pair<int, int>> q;
		memset(vis, 0, sizeof vis); // 清空之前的数据
		q.push({ bx, by });
		vis[bx][by] = true;
		int step = 0;
		while (q.size())
		{
			step++;
			int sz = q.size();
			while (sz--)
			{
				auto [a, b] = q.front();
				q.pop();
				for (int i = 0; i < 4; i++)
				{
					int x = a + dx[i], y = b + dy[i];
					if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] && !vis[x]
						[y])
					{
						if (x == ex && y == ey) return step;
						q.push({ x, y });
						vis[x][y] = true;
					}
				}
			}
		}
		return -1;
	}
};